# -*- coding:utf-8 -*-


""" 题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
"""

""" 思路解析

类似于二分查找，根据题目，如果拿数组中任意一个元素与目标数值进行比较，如果该元素小于目标数值，那么目标数值一定是在该元素的下方或右方，如果大于目标数值，那么目标数值一定在该元素的上方或者左方。

对于二分查找来说，每次比较只能移动一个指针，同时，指针的移动方向必须在查找过程中保持一致。在二维数组的查找中，两个指针是一个上下方向移动，一个是左右方向移动的。两个指针可以从同一个角出发，也可以从不同的角出发。这里我们只考虑从同一个角出发的情况。

假设我们从左上角出发，也就是row=0 和 col=0，如果元素小于目标数值，我们会将row往下移或着col往右移，这样，被屏蔽的区域可能会是目标元素所在的区域。比如row+=1，那么第一行除左上角以外的元素就被忽略了，如果col+=1，那么第一列出左上角以外的元素就被忽略了。因此这样是不可行的。

所以本题从右上角出发寻找解题思路，即开始时col=len(array[0])-1,row=0,col往左移动，row往下移动，当某元素小于目标数值时，col-=1，而当某元素大于目标数值时，row+=1。

"""


class Solution:
    # array 二维列表
    def find(self, target, array):
        # write code here
        if not array:
            return False

        r = 0
        c = len(array[0]) - 1
        while r <= len(array[0]) - 1 and c >= 0:
            if target == array[r][c]:
                return True
            elif target > array[r][c]:
                r += 1
            elif target < array[r][c]:
                c -= 1
        return False